home *** CD-ROM | disk | FTP | other *** search
/ Chip 2007 January, February, March & April / Chip-Cover-CD-2007-02.iso / Pakiet bezpieczenstwa / mini Pentoo LiveCD 2006.1 / mpentoo-2006.1.iso / livecd.squashfs / usr / lib / mozilla-firefox / include / xpcom / nsVoidArray.h < prev    next >
C/C++ Source or Header  |  2006-05-08  |  13KB  |  407 lines
  1. /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2; c-file-offsets: ((substatement-open . 0))  -*- */
  2. /* ***** BEGIN LICENSE BLOCK *****
  3.  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
  4.  *
  5.  * The contents of this file are subject to the Mozilla Public License Version
  6.  * 1.1 (the "License"); you may not use this file except in compliance with
  7.  * the License. You may obtain a copy of the License at
  8.  * http://www.mozilla.org/MPL/
  9.  *
  10.  * Software distributed under the License is distributed on an "AS IS" basis,
  11.  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  12.  * for the specific language governing rights and limitations under the
  13.  * License.
  14.  *
  15.  * The Original Code is mozilla.org code.
  16.  *
  17.  * The Initial Developer of the Original Code is
  18.  * Netscape Communications Corporation.
  19.  * Portions created by the Initial Developer are Copyright (C) 1998
  20.  * the Initial Developer. All Rights Reserved.
  21.  *
  22.  * Contributor(s):
  23.  *
  24.  * Alternatively, the contents of this file may be used under the terms of
  25.  * either of the GNU General Public License Version 2 or later (the "GPL"),
  26.  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  27.  * in which case the provisions of the GPL or the LGPL are applicable instead
  28.  * of those above. If you wish to allow use of your version of this file only
  29.  * under the terms of either the GPL or the LGPL, and not to allow others to
  30.  * use your version of this file under the terms of the MPL, indicate your
  31.  * decision by deleting the provisions above and replace them with the notice
  32.  * and other provisions required by the GPL or the LGPL. If you do not delete
  33.  * the provisions above, a recipient may use your version of this file under
  34.  * the terms of any one of the MPL, the GPL or the LGPL.
  35.  *
  36.  * ***** END LICENSE BLOCK ***** */
  37. #ifndef nsVoidArray_h___
  38. #define nsVoidArray_h___
  39.  
  40. //#define DEBUG_VOIDARRAY 1
  41.  
  42. #include "nscore.h"
  43. #include "nsAString.h"
  44.  
  45. // Comparator callback function for sorting array values.
  46. typedef int (* PR_CALLBACK nsVoidArrayComparatorFunc)
  47.             (const void* aElement1, const void* aElement2, void* aData);
  48.  
  49. // Enumerator callback function. Return PR_FALSE to stop
  50. typedef PRBool (* PR_CALLBACK nsVoidArrayEnumFunc)(void* aElement, void *aData);
  51.  
  52. /// A basic zero-based array of void*'s that manages its own memory
  53. class NS_COM nsVoidArray {
  54. public:
  55.   nsVoidArray();
  56.   nsVoidArray(PRInt32 aCount);  // initial count of aCount elements set to nsnull
  57.   virtual ~nsVoidArray();
  58.  
  59.   nsVoidArray& operator=(const nsVoidArray& other);
  60.  
  61.   inline PRInt32 Count() const {
  62.     return mImpl ? mImpl->mCount : 0;
  63.   }
  64.   // returns the max number that can be held without allocating
  65.   inline PRInt32 GetArraySize() const {
  66.     return mImpl ? (PRInt32(mImpl->mBits) & kArraySizeMask) : 0;
  67.   }
  68.  
  69.   void* FastElementAt(PRInt32 aIndex) const
  70.   {
  71.     NS_ASSERTION(0 <= aIndex && aIndex < Count(), "index out of range");
  72.     return mImpl->mArray[aIndex];
  73.   }
  74.  
  75.   // This both asserts and bounds-checks, because (1) we don't want
  76.   // people to write bad code, but (2) we don't want to change it to
  77.   // crashing for backwards compatibility.  See bug 96108.
  78.   void* ElementAt(PRInt32 aIndex) const
  79.   {
  80.     NS_ASSERTION(0 <= aIndex && aIndex < Count(), "index out of range");
  81.     return SafeElementAt(aIndex);
  82.   }
  83.  
  84.   // bounds-checked version
  85.   void* SafeElementAt(PRInt32 aIndex) const
  86.   {
  87.     if (PRUint32(aIndex) >= PRUint32(Count())) // handles aIndex < 0 too
  88.     {
  89.       return nsnull;
  90.     }
  91.     // The bounds check ensures mImpl is non-null.
  92.     return mImpl->mArray[aIndex];
  93.   }
  94.  
  95.   void* operator[](PRInt32 aIndex) const { return ElementAt(aIndex); }
  96.  
  97.   PRInt32 IndexOf(void* aPossibleElement) const;
  98.  
  99.   PRBool InsertElementAt(void* aElement, PRInt32 aIndex);
  100.   PRBool InsertElementsAt(const nsVoidArray &other, PRInt32 aIndex);
  101.  
  102.   PRBool ReplaceElementAt(void* aElement, PRInt32 aIndex);
  103.  
  104.   // useful for doing LRU arrays, sorting, etc
  105.   PRBool MoveElement(PRInt32 aFrom, PRInt32 aTo);
  106.  
  107.   PRBool AppendElement(void* aElement) {
  108.     return InsertElementAt(aElement, Count());
  109.   }
  110.  
  111.   PRBool AppendElements(nsVoidArray& aElements) {
  112.     return InsertElementsAt(aElements, Count());
  113.   }
  114.  
  115.   PRBool RemoveElement(void* aElement);
  116.   PRBool RemoveElementsAt(PRInt32 aIndex, PRInt32 aCount);
  117.   PRBool RemoveElementAt(PRInt32 aIndex) { return RemoveElementsAt(aIndex,1); }
  118.  
  119.   virtual void   Clear();
  120.  
  121.   virtual PRBool SizeTo(PRInt32 aMin);
  122.   // Subtly different - Compact() tries to be smart about whether we
  123.   // should reallocate the array; SizeTo() just does it.
  124.   virtual void Compact();
  125.  
  126.   void Sort(nsVoidArrayComparatorFunc aFunc, void* aData);
  127.  
  128.   PRBool EnumerateForwards(nsVoidArrayEnumFunc aFunc, void* aData);
  129.   PRBool EnumerateBackwards(nsVoidArrayEnumFunc aFunc, void* aData);
  130.  
  131. protected:
  132.   virtual PRBool GrowArrayBy(PRInt32 aGrowBy);
  133.  
  134.   struct Impl {
  135.     /**
  136.      * Packed bits. The low 31 bits are the array's size.
  137.      * The highest bit is a flag that indicates 
  138.      * whether or not we "own" mArray, and must free() it when
  139.      * destroyed.
  140.      */
  141.     PRUint32 mBits;
  142.  
  143.     /**
  144.      * The number of elements in the array
  145.      */
  146.     PRInt32 mCount;
  147.  
  148.     /**
  149.      * Array data, padded out to the actual size of the array.
  150.      */
  151.     void*   mArray[1];
  152.   };
  153.  
  154.   Impl* mImpl;
  155. #if DEBUG_VOIDARRAY
  156.   PRInt32 mMaxCount;
  157.   PRInt32 mMaxSize;
  158.   PRBool  mIsAuto;
  159. #endif
  160.  
  161.   enum {
  162.     kArrayOwnerMask = 1 << 31,
  163.     kArraySizeMask = ~kArrayOwnerMask
  164.   };
  165.  
  166.  
  167.   // bit twiddlers
  168.   void SetArray(Impl *newImpl, PRInt32 aSize, PRInt32 aCount, PRBool owner);
  169.   inline PRBool IsArrayOwner() const {
  170.     return mImpl ? (PRBool(mImpl->mBits) & kArrayOwnerMask) : PR_FALSE;
  171.   }
  172.  
  173. private:
  174.   /// Copy constructors are not allowed
  175.   nsVoidArray(const nsVoidArray& other);
  176. };
  177.  
  178.  
  179. // A zero-based array with a bit of automatic internal storage
  180. class NS_COM nsAutoVoidArray : public nsVoidArray {
  181. public:
  182.   nsAutoVoidArray();
  183.   void Clear();
  184.  
  185.   virtual PRBool SizeTo(PRInt32 aMin);
  186.   virtual void Compact();
  187.   
  188. protected:
  189.   // The internal storage
  190.   enum { kAutoBufSize = 8 };
  191.   char mAutoBuf[sizeof(Impl) + (kAutoBufSize - 1) * sizeof(void*)];
  192. };
  193.  
  194.  
  195. class nsString;
  196.  
  197. typedef int (* PR_CALLBACK nsStringArrayComparatorFunc)
  198.             (const nsString* aElement1, const nsString* aElement2, void* aData);
  199.  
  200. typedef PRBool (*nsStringArrayEnumFunc)(nsString& aElement, void *aData);
  201.  
  202. class NS_COM nsStringArray: protected nsVoidArray
  203. {
  204. public:
  205.   nsStringArray(void);
  206.   nsStringArray(PRInt32 aCount);  // Storage for aCount elements will be pre-allocated
  207.   virtual ~nsStringArray(void);
  208.  
  209.   nsStringArray& operator=(const nsStringArray& other);
  210.  
  211.   PRInt32 Count(void) const {
  212.     return nsVoidArray::Count();
  213.   }
  214.  
  215.   void StringAt(PRInt32 aIndex, nsAString& aString) const;
  216.   nsString* StringAt(PRInt32 aIndex) const;
  217.   nsString* operator[](PRInt32 aIndex) const { return StringAt(aIndex); }
  218.  
  219.   PRInt32 IndexOf(const nsAString& aPossibleString) const;
  220.  
  221.   PRBool InsertStringAt(const nsAString& aString, PRInt32 aIndex);
  222.  
  223.   PRBool ReplaceStringAt(const nsAString& aString, PRInt32 aIndex);
  224.  
  225.   PRBool AppendString(const nsAString& aString) {
  226.     return InsertStringAt(aString, Count());
  227.   }
  228.  
  229.   PRBool RemoveString(const nsAString& aString);
  230.   PRBool RemoveStringAt(PRInt32 aIndex);
  231.   void   Clear(void);
  232.  
  233.   void Compact(void) {
  234.     nsVoidArray::Compact();
  235.   }
  236.  
  237.   void Sort(void);
  238.   void Sort(nsStringArrayComparatorFunc aFunc, void* aData);
  239.  
  240.   PRBool EnumerateForwards(nsStringArrayEnumFunc aFunc, void* aData);
  241.   PRBool EnumerateBackwards(nsStringArrayEnumFunc aFunc, void* aData);
  242.  
  243. private:
  244.   /// Copy constructors are not allowed
  245.   nsStringArray(const nsStringArray& other);
  246. };
  247.  
  248.  
  249. class nsCString;
  250.  
  251. typedef int (* PR_CALLBACK nsCStringArrayComparatorFunc)
  252.             (const nsCString* aElement1, const nsCString* aElement2, void* aData);
  253.  
  254. typedef PRBool (*nsCStringArrayEnumFunc)(nsCString& aElement, void *aData);
  255.  
  256. class NS_COM nsCStringArray: protected nsVoidArray
  257. {
  258. public:
  259.   nsCStringArray(void);
  260.   nsCStringArray(PRInt32 aCount); // Storage for aCount elements will be pre-allocated
  261.   virtual ~nsCStringArray(void);
  262.  
  263.   nsCStringArray& operator=(const nsCStringArray& other);
  264.  
  265.   // Parses a given string using the delimiter passed in. If the array
  266.   // already has some elements, items parsed from string will be appended 
  267.   // to array. For example, array.ParseString("a,b,c", ","); will add strings
  268.   // "a", "b" and "c" to the array. Parsing process has the same tokenizing 
  269.   // behavior as strtok().  
  270.   void ParseString(const char* string, const char* delimiter);
  271.  
  272.   PRInt32 Count(void) const {
  273.     return nsVoidArray::Count();
  274.   }
  275.  
  276.   void CStringAt(PRInt32 aIndex, nsACString& aCString) const;
  277.   nsCString* CStringAt(PRInt32 aIndex) const;
  278.   nsCString* operator[](PRInt32 aIndex) const { return CStringAt(aIndex); }
  279.  
  280.   PRInt32 IndexOf(const nsACString& aPossibleString) const;
  281.   PRInt32 IndexOfIgnoreCase(const nsACString& aPossibleString) const;
  282.  
  283.   PRBool InsertCStringAt(const nsACString& aCString, PRInt32 aIndex);
  284.  
  285.   PRBool ReplaceCStringAt(const nsACString& aCString, PRInt32 aIndex);
  286.  
  287.   PRBool AppendCString(const nsACString& aCString) {
  288.     return InsertCStringAt(aCString, Count());
  289.   }
  290.  
  291.   PRBool RemoveCString(const nsACString& aCString);
  292.   PRBool RemoveCStringIgnoreCase(const nsACString& aCString);
  293.   PRBool RemoveCStringAt(PRInt32 aIndex);
  294.   void   Clear(void);
  295.  
  296.   void Compact(void) {
  297.     nsVoidArray::Compact();
  298.   }
  299.  
  300.   void Sort(void);
  301.   void SortIgnoreCase(void);
  302.   void Sort(nsCStringArrayComparatorFunc aFunc, void* aData);
  303.  
  304.   PRBool EnumerateForwards(nsCStringArrayEnumFunc aFunc, void* aData);
  305.   PRBool EnumerateBackwards(nsCStringArrayEnumFunc aFunc, void* aData);
  306.  
  307. private:
  308.   /// Copy constructors are not allowed
  309.   nsCStringArray(const nsCStringArray& other);
  310. };
  311.  
  312.  
  313. //===================================================================
  314. //  nsSmallVoidArray is not a general-purpose replacement for
  315. //  ns(Auto)VoidArray because there is (some) extra CPU overhead for arrays
  316. //  larger than 1 element, though not a lot.  It is appropriate for
  317. //  space-sensitive uses where sizes of 0 or 1 are moderately common or
  318. //  more, and where we're NOT storing arbitrary integers or arbitrary
  319. //  pointers.
  320.  
  321. // NOTE: nsSmallVoidArray can ONLY be used for holding items that always
  322. // have the low bit as a 0 - i.e. element & 1 == 0.  This happens to be
  323. // true for allocated and object pointers for all the architectures we run
  324. // on, but conceivably there might be some architectures/compilers for
  325. // which it is NOT true.  We know this works for all existing architectures
  326. // because if it didn't then nsCheapVoidArray would have failed.  Also note
  327. // that we will ASSERT if this assumption is violated in DEBUG builds.
  328.  
  329. // XXX we're really re-implementing the whole nsVoidArray interface here -
  330. // some form of abstract class would be useful
  331.  
  332. // I disagree on the abstraction here.  If the point of this class is to be
  333. // as small as possible, and no one will ever derive from it, as I found
  334. // today, there should not be any virtualness to it to avoid the vtable
  335. // ptr overhead.
  336.  
  337. class NS_COM nsSmallVoidArray
  338. {
  339. public:
  340.   nsSmallVoidArray();
  341.   ~nsSmallVoidArray();
  342.  
  343.   nsSmallVoidArray& operator=(nsSmallVoidArray& other);
  344.   void* operator[](PRInt32 aIndex) const { return ElementAt(aIndex); }
  345.  
  346.   PRInt32 GetArraySize() const;
  347.  
  348.   PRInt32 Count() const;
  349.   void* ElementAt(PRInt32 aIndex) const;
  350.   void* SafeElementAt(PRInt32 aIndex) const {
  351.     // let compiler inline; it may be able to remove these checks
  352.     if (aIndex < 0 || aIndex >= Count())
  353.       return nsnull;
  354.     return ElementAt(aIndex);
  355.   }
  356.   PRInt32 IndexOf(void* aPossibleElement) const;
  357.   PRBool InsertElementAt(void* aElement, PRInt32 aIndex);
  358.   PRBool InsertElementsAt(const nsVoidArray &other, PRInt32 aIndex);
  359.   PRBool ReplaceElementAt(void* aElement, PRInt32 aIndex);
  360.   PRBool MoveElement(PRInt32 aFrom, PRInt32 aTo);
  361.   PRBool AppendElement(void* aElement);
  362.   PRBool AppendElements(nsVoidArray& aElements) {
  363.     return InsertElementsAt(aElements, Count());
  364.   }
  365.   PRBool RemoveElement(void* aElement);
  366.   PRBool RemoveElementsAt(PRInt32 aIndex, PRInt32 aCount);
  367.   PRBool RemoveElementAt(PRInt32 aIndex);
  368.  
  369.   void Clear();
  370.   PRBool SizeTo(PRInt32 aMin);
  371.   void Compact();
  372.   void Sort(nsVoidArrayComparatorFunc aFunc, void* aData);
  373.  
  374.   PRBool EnumerateForwards(nsVoidArrayEnumFunc aFunc, void* aData);
  375.   PRBool EnumerateBackwards(nsVoidArrayEnumFunc aFunc, void* aData);
  376.  
  377. private:
  378.   typedef unsigned long PtrBits;
  379.  
  380.   PRBool HasSingleChild() const
  381.   {
  382.     return (mChildren && (PtrBits(mChildren) & 0x1));
  383.   }
  384.   PRBool HasVector() const
  385.   {
  386.     return (mChildren && !(PtrBits(mChildren) & 0x1));
  387.   }
  388.   void* GetSingleChild() const
  389.   {
  390.     return (mChildren ? ((void*)(PtrBits(mChildren) & ~0x1)) : nsnull);
  391.   }
  392.   void SetSingleChild(void *aChild);
  393.   nsVoidArray* GetChildVector() const
  394.   {
  395.     return (nsVoidArray*)mChildren;
  396.   }
  397.   nsVoidArray* SwitchToVector();
  398.  
  399.   // A tagged pointer that's either a pointer to a single child
  400.   // or a pointer to a vector of multiple children. This is a space
  401.   // optimization since a large number of containers have only a 
  402.   // single child.
  403.   void *mChildren;  
  404. };
  405.  
  406. #endif /* nsVoidArray_h___ */
  407.